package com.dataStructures.sort;

import java.util.Arrays;

/**
 * 插入排序（时间复杂度 O(n^2)）
 */
public class InsertSort {
	public static void main(String[] args) {
		int[] arr = {3, 9, -1, 10, 20};
		System.out.println("排序前：" + Arrays.toString(arr));
		insertSort(arr);
		System.out.println("排序后：" + Arrays.toString(arr));

		// 批量测试
		int[] arrBatch = new int[10000000];
		for (int i = 0; i < 10000000; i++) {
			arrBatch[i] = (int) (Math.random() * 10000000);
		}
		long begin = System.currentTimeMillis();
		insertSort(arrBatch);
		System.out.println("coast time:" + (System.currentTimeMillis() - begin));
	}

	public static void insertSort(int[] arr) {
		// 待插入数的位置
		int insertIndex;
		// 待插入数的值
		int insertVal;
		// 从第二个数开始，逐次寻找插入的位置
		for (int i = 1; i < arr.length; i++) {
			// 待插入的数的值
			insertVal = arr[i];
			// 首次待插入的位置 是 此数前边一个数的位置
			insertIndex = i - 1;

			// insertIndex >= 0：控制边界，insertVal < arr[insertIndex]：比较值，找到插入位置
			while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
				// 把前边一个数的位置后移（前边那个数的值复制给后边这个数）
				/*
				    数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是: {2,3,4,5,6,6}
					{2,3,4,5,5,6}
					{2,3,4,4,5,6}
					{2,3,3,4,5,6}
					{2,2,3,4,5,6}
					{1,2,3,4,5,6}
				 */
				arr[insertIndex + 1] = arr[insertIndex];
				// 继续往前找
				insertIndex--;
			}
			// 当退出 while 循环时，说明插入的位置找到, insertIndex + 1
			if (insertIndex + 1 != i) {
				arr[insertIndex + 1] = insertVal;
			}
		}
	}
}
